package com.hqq.exercise.tree;

import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingDeque;

/**
 * MirrorTree 二叉树的镜像
 * 题目描述:
 * 请完成一个函数，输入一个二叉树，该函数输出它的镜像。
 * 思路:
 * 遍历两个二叉树 如果当前节点存在子节点的话 就交换它的两个子节点
 * Created by heqianqian on 2017/8/12.
 */
public class MirrorTree {

    /**
     * 输出一个二叉树的镜像[递归]
     *
     * @param root 二叉树的根节点
     */
    public static void mirrorTreeByRecursion(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            return;
        }
        //如果存在子节点 那么就交换它的两个子节点
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        if (root.left != null) {
            mirrorTreeByRecursion(root.left);
        }

        if (root.right != null) {
            mirrorTreeByRecursion(root.right);
        }
    }

    /**
     * 输出一个二叉树的镜像[循环] 【层序遍历+队列】
     * 使用队列实现
     * 我们按照[广度遍历]二叉树的顺序，逐个处理遍历的节点。
     * 当处理的当前节点，如果有孩子节点，我们交换它们的孩子节点，并且把它们的非空孩子入[队列]。
     * 处理完当前节点以后，我们下一次处理队头的节点。
     *
     * @param root 二叉树的根节点
     *
     */
    public static void mirrorTreeByLoopLevelTraversal(TreeNode root) {
        Queue<TreeNode> treeNodeQueue = new LinkedBlockingDeque<>();
        while (root != null) {
            if (root.left != null && root.right != null) {
                TreeNode temp = root.left;
                root.left = root.right;
                root.right = temp;
            }
            if (root.left != null) {
                treeNodeQueue.add(root.left);
            }
            if (root.right != null) {
                treeNodeQueue.add(root.right);
            }
            if (!treeNodeQueue.isEmpty()) {
                root = treeNodeQueue.poll();
            } else {
                break;
            }
        }
    }

    /**
     * 输出一个二叉树的镜像[循环] 【先序遍历+栈】
     * 使用堆栈实现
     * 我们按照[先序遍历]二叉树的顺序，逐个处理遍历的节点。
     * 当处理的当前节点，如果有孩子节点，我们交换它们的孩子节点，并且把它们的非空孩子入[栈]
     * 处理完当前节点以后，我们下一次处理队头的节点。
     *
     * @param root 二叉树的根节点
     */
    public static void mirrorTreeByLoopPreTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode temp = null;
        TreeNode t = null;
        while (!stack.isEmpty()) {
            temp = stack.pop();
            //如果temp的左右子树不为空 那么交换左右子树
            if (temp.left != null && temp.right != null) {
                t = temp.left;
                temp.left = temp.right;
                temp.right = t;
            }
            //如果左子树不为空 左子树入栈
            if (temp.left != null) {
                stack.push(temp.left);
            }
            //如果右子树不为空 右子树入栈
            if (temp.right != null) {
                stack.push(temp.right);
            }
        }
    }
}
